
/**
 * 根据动态规划的逻辑，我们可以这样计算
 * dp[i] = Math.max(dp[i], dp[i - oilRequired] + profit) 
 * 表示表示如果收割机选择收割当前考虑的地块（耗油量为 oilRequired，收益为 profit），
 * 那么收割后剩余油量为 i - oilRequired，
 * 加上这次收割的收益 profit，得到收割这个地块后的总收益;
 * 因此我们计算
 * dp[1] 只能选择第一个地块，收益为 1。
 * dp[2] 当选择耗油为1的地块时，dp[2] = Math.max(dp[2], dp[2 - 1] + 1)=2;
 *  dp[2]当选择耗油为2的地块时，dp[2] = Math.max(dp[2], dp[2 - 2] + 4)=4;
 * 
 * dp[3] 当选择耗油为1的地块时，dp[3] = Math.max(dp[3], dp[3 - 1] + 1)=5;
 *  dp[3]当选择耗油为2的地块时，dp[3] = Math.max(dp[3], dp[3 - 2] + 4)=5;
 *  dp[3]当选择耗油为3的地块时，dp[3] = Math.max(dp[3], dp[3 - 3] + 5)=5;
 * 
 * dp[4] 当选择耗油为1的地块时，dp[4] = Math.max(dp[4], dp[4 - 1] + 1)=6;
 *  dp[4]当选择耗油为2的地块时，dp[4] = Math.max(dp[4], dp[4 - 2] + 4)=8;
 *  dp[4]当选择耗油为3的地块时，dp[4] = Math.max(dp[4], dp[4 - 3] + 5)=6;
 * 
 *  以此类推计算所有情况
 */

var  getMaxProfit =function(plots, oil) {
  // 去除重复地块并按耗油量排序
  let set = new Set();
  let uniquePlots =plots.filter((item,index)=>{
    if(!set.has(item[0])){
      set.add(item[0])
      return item
    }
  })
  let sortPlots = uniquePlots.sort((a,b)=>a[0]-b[0])

  // 初始化动态规划数组
  let dp = new Array(oil + 1).fill(0);

  // 动态规划计算最大收益
  for (let i = 1; i <= oil; i++) {

    // 遍历 sortPlots 得到当i不同时，不同地块的收益
    const profitMap = sortPlots.map((plot,index) => {
      var profit = 0
      if(plot[0]<=i){
         profit =  dp[i - plot[0]] + plot[1] ;
      }else{
        profit =  0 ;
      }
       return profit
    });

    // 排序取得最大值
    var sortProfit = profitMap.sort((a,b)=>b-a)

    // 比较 dp[i] 和sortProfit 的值
    dp[i] = Math.max(dp[i],sortProfit[0]);

  }

  return dp[oil];
}

let plots = [[1,1], [7,9], [6,10], [2,4], [3,5], [6,10]];
// 给定油量
let oil = 10;

// 计算最大收益
let maxProfit = getMaxProfit(plots, 10);
console.log(maxProfit)
